This invention relates to a method of detecting errors, and in particular, to a method of detecting anomalies in an event stream such as in data reception on a modem or in detection of possible intruders in a secure network.
In the transmission of large amounts of data via modem or within a network of computers, methods have been used to determine whether or not the transmission is proceeding successfully. If such methods detect that a stream of data is likely to have errors, then a warning is sent to alert the user such as a system administrator so that he can decide whether or not to terminate the transmission and correct the problem giving rise to the errors.
In addition, in security audit trail analysis, data or activities within a secure system are analyzed in order to uncover anomalies which may warrant further investigation in order to determine whether the security of the network is being compromised. One approach, described in Security Audit Trail Analysis Using Inductively Generated Predictive Rules, by Teng et al., IEEE Journal, p. 24, 1990, uses patterns as a profile for anomaly detection in order to allow a security auditing system to capture characteristics of user behavior which may be erratic from a statistical point of view, using traditional statistical approaches. When these methods detect a possible intrusion into a network, a warning is sent to alert a system administrator.
Both of these applications, as well as many others, benefit from the application of general methods of detecting anomalies. As described in Structural properties of the String Statistics Problem, by A. Apostolic et al, Journal of Computer and Systems Sciences, vol. 31, no. 2, p. 394-411 and in An Inductive Engine for the Acquisition of Temporal Knowledge, Ph. D. Thesis, by K. Chen; Dept. Of Comp. Sci. at University of Illinois at Urbana-Champaign, 1988, rules have been used for anomaly detection. Further, there exists a high-level programming language, namely Prolog, which is used to invoke rules. In addition, as described in Detection of Anomalous Computer Session Activity, by H. S. Vaccaro and G. E. Liepins, Proc. IEEE Symp. On Res. in Sec. & Privacy, pp. 280-89, Oakland, 1989, trees have been used for anomaly detection, but only for consistency with a single audit record, not across a sequence of records. Still further, according to Efficient String Matching: an aid to Bibliographic Search, by A. V. Aho and M. J. Corasick, Communications of the ACM, vol. 18, no. 6, pp. 333-40, June 1975, Automatons have been used for string searching.
The above methods provides inputs which are useful in anomaly detection. However, they do not provide for fully integrated anomaly detection.
Therefore, what is needed is a fully integrated method based on simpler structures which will permit an analyst to go much farther in detecting anomalies representative of system security breaches.